#include <iostream>
#define _USE_MATH_DEFINES
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

struct FPOINT{double x, y;};
struct FRECT{double xmin, ymin, xmax, ymax;};
template <class T>

// basic
inline bool Between(T t, T t1, T t2)
{return t>t1 && t<t2;}
inline double sqr(double d){return d*d;}
inline double distance(double x1, double y1, double x2, double y2)
{ return sqrt(sqr(x1-x2)+sqr(y1-y2)); }
 


const double M_PI2=2*M_PI;
const FRECT RECT_EMPTY={1e9, 1e9, -1e9, -1e9};
const FRECT RECT_FULL={1e-9, 1e-9, 1e9, 1e9};
bool IsPointInRect(double x, double y,const FRECT& frc2)
{
	return Between(x, frc2.xmin, frc2.xmax)
		&& Between(y, frc2.ymin, frc2.ymax);
}
void ExpandRectToIncludePoint(FRECT& frc, const FPOINT& fpt)
{
	frc.xmin=min(frc.xmin, fpt.x);
	frc.xmax=max(frc.xmax, fpt.x);
	frc.ymin=min(frc.ymin, fpt.y);
	frc.ymax=max(frc.ymax, fpt.y);
}

double Angle2D(double x1, double y1, double x2, double y2)
{
	double a1=atan2(x1,y1);
	double a2=atan2(x2,y2);
	double da=a2-a1;
	while(da>M_PI)da-=M_PI2;
	while(da<-M_PI)da+=M_PI2;
	return da;
}

bool IsPointInPolygon(double x, double y,const FPOINT pts[], int npts)
{
	// first try to accellerate with bounding 
	FRECT frc=RECT_EMPTY; // use a invalid rect
	for(int i=0;i<npts;i++)
		ExpandRectToIncludePoint(frc, pts[i]);

	if(!IsPointInRect(x, y, frc))
		return false;

	double dAngle=0;
	for(int i=0;i<npts;i++)
	{
		int j=(i+1)%npts;

		double x1=pts[i].x;
		double y1=pts[i].y;
		double x2=pts[j].x;
		double y2=pts[j].y;

		x1-=x; x2-=x;
		y1-=y; y2-=y;

		dAngle+=Angle2D(x1,y1,x2,y2);
	}
	return fabs((fabs(dAngle) - M_PI2))<1e-9; // maybe in anti-clockwise
}


// utils functions for this function
namespace
{
	template <typename T>
	inline int sgn(T t)
	{
		return t>0?1:(t<0?-1:0);
	}
	inline bool inrange(double d, double d1, double d2)
	{
		return (d>=d1 && d<=d2) || (d<=d1 && d>=d2);
	}

	// test whether two line intersect
	bool lineline_intersection(double x1, double y1, double x2, double y2,
							double x3, double y3, double x4, double y4,
							double& x, double& y)
	{
		const double epsinon=1e-9;
		double u_base=(y4-y3)*(x2-x1)-(x4-x3)*(y2-y1);
		if(fabs(u_base)<epsinon)
			return false;

		double ua=(x4-x3)*(y1-y3)-(y4-y3)*(x1-x3);
		double ub=(x2-x1)*(y1-y3)-(y2-y1)*(x1-x3);
		ua/=u_base;
		ub/=u_base;
		x=x1+ua*(x2-x1);
		y=y1+ub*(y2-y1);
		return true;
	}

	// test whether two segments intersect
	bool segseg_intersection(double x1, double y1, double x2, double y2,
						double x3, double y3, double x4, double y4,
						double& x, double& y)
	{
		if(!lineline_intersection(x1, y1, x2, y2, x3, y3, x4, y4, x, y))
			return false;
		return inrange(x, x1, x2)
			&& inrange(y, y1, y2)
			&& inrange(x, x3, x4)
			&& inrange(y, y3, y4);
	}

	// test whether a segment and a line intersect
	bool segline_intersection(double x1, double y1, double x2, double y2,
						double x3, double y3, double x4, double y4,
						double& x, double& y)
	{
		if(!lineline_intersection(x1, y1, x2, y2, x3, y3, x4, y4, x, y))
			return false;
		return inrange(x, x1, x2)
			&& inrange(y, y1, y2);
	}

	struct sDiscCompare
	{
		double cx, cy; // the center point
		sDiscCompare(double cx, double cy)
		{
			this->cx=cx;
			this->cy=cy;
		}
		bool operator()(const FPOINT& fpt1, const FPOINT& fpt2)
		{
			double _2d1=sqr(cx-fpt1.x)+sqr(cy-fpt1.y);
			double _2d2=sqr(cx-fpt2.x)+sqr(cy-fpt2.y);
			return _2d1<_2d2;
		}
	};
	bool fXYCompare(const FPOINT& fpt1, const FPOINT& fpt2)
	{
		if(fpt1.x<fpt2.x)
			return true;
		else if(fpt1.x>fpt2.x)
			return false;
		else
			return fpt1.y<fpt2.y;
	}
}

bool IsSegmentInPolygon(const FPOINT& fpt1, const FPOINT& fpt2, const FPOINT* pPoints, int nPoints)
{
	// first the two ends must be in the polygon
	if(!IsPointInPolygon(fpt1.x, fpt1.y, pPoints, nPoints)
		|| !IsPointInPolygon(fpt2.x, fpt2.y, pPoints, nPoints))
		return false;

	vector<FPOINT> vInters;
	for(int i=0;i<nPoints;i++)
	{
		int j=(i+1)%nPoints;
		FPOINT fpt;
		if(segseg_intersection(fpt1.x, fpt1.y, fpt2.x, fpt2.y,
			pPoints[i].x, pPoints[i].y, pPoints[j].x, pPoints[j].y,
			fpt.x, fpt.y))
			vInters.push_back(fpt);
	}

	// sort the points
	sort(vInters.begin(), vInters.end(), fXYCompare);

	// test if all middle points are in the polygon
	for(size_t i=0;i<vInters.size();i++)
	{
		size_t j=(i+1)%vInters.size();
		double xm=(vInters[i].x+vInters[j].x)/2;
		double ym=(vInters[i].y+vInters[j].y)/2;
		if(!IsPointInPolygon(xm, ym, pPoints, nPoints))
			return false;
	}
	return true;
}

bool IsPolygonInPolygon(const FPOINT* pPointsTest, int nPointsTest, const FPOINT* pPoints, int nPoints)
{
	// test if all edges are in the polygon
	for(int i=0;i<nPointsTest;i++)
	{
		int j=(i+1)%4;
		if(!IsSegmentInPolygon(pPointsTest[i], pPointsTest[j], pPoints, nPoints))
			return false;
	}
	return true;
}
